A computer network is a geographically distributed collection of interconnected communication links used to transport data between nodes, such as computers. Many types of computer networks are available, with the types ranging from local area networks (LANs) to wide area networks (WANs). The nodes typically communicate by exchanging discrete packets or messages of data according to pre-defined protocols. In this context, a protocol consists of a set of rules defining how the nodes interact with each other.
Computer networks may be further interconnected by intermediate nodes, such as routers, to extend the effective “size” of each network. Since management of a large system of interconnected computer networks can prove burdensome, smaller groups of computer networks may be maintained as routing domains or autonomous systems. The networks within an autonomous system are typically coupled together by conventional “intradomain” routers. Yet it still may be desirable to increase the number of nodes capable of exchanging data; in this case, “interdomain” routers executing interdomain routing protocols are used to interconnect nodes of the various autonomous systems.
An example of an interdomain routing protocol is the Border Gateway Protocol version 4 (BGP), which performs routing between autonomous systems by exchanging routing and reachability information among neighboring interdomain routers of the systems. An adjacency is a relationship formed between selected neighboring (peer) routers for the purpose of exchanging routing information messages and abstracting the network topology. Before transmitting such messages, however, the peers cooperate to establish a logical “peer” connection (session) between the routers. BGP generally operates over a reliable transport protocol, such as the Transmission Control Protocol (TCP), to establish a TCP connection/session.
The BGP routing protocol is well known and described in detail in Request For Comments (RFC) 1771, by Y. Rekhter and T. Li (1995), Internet Draft <draft-ietf-idr-bgp4-20.txt> titled, A Border Gateway Protocol 4 (BGP-4) by Y. Rekhter and T. Li (April 2003) and Interconnections, Bridges and Routers, by R. Perlman, published by Addison Wesley Publishing Company, at pages 323-329 (1992), all disclosures of which are hereby incorporated by reference.
The interdomain routers configured to execute an implementation of the BGP protocol, referred to herein as BGP routers, perform various routing functions, including transmitting and receiving routing messages and rendering routing decisions based on routing metrics. Each BGP router maintains a routing table that lists all feasible paths to a particular network. Periodic refreshing of the routing table is generally not performed; however, BGP peer routers residing in the autonomous systems (“domains”) exchange routing information under certain circumstances. For example, when a BGP router initially connects to the network, the peer routers exchange the entire contents of their routing tables. Thereafter, when changes occur to those contents, the routers exchange only those portions of their routing tables that change in order to update their peers' tables. These update messages are thus incremental update messages sent in response to changes to the contents of the routing tables and advertise only a best path to a particular network node.
The routing information exchanged by BGP peer routers typically includes destination address prefixes, i.e., the portions of destination addresses used by the routing protocol to render routing (“next hop”) decisions. Examples of such destination addresses include Internet Protocol (IP) version 4 (IPv4) and version 6 (IPv6) addresses.
Broadly stated, a BGP router generates routing update messages for an adjacency or peer router by “walking-through” the routing table and applying appropriate routing policies. A routing policy is information that enables a BGP router to rank routes according to filtering and preference (i.e., the “best route”). Routing updates provided by the update messages allow BGP routers of the autonomous systems to construct a consistent view of the network topology. The update messages are typically sent using a reliable transport, such as TCP, to ensure reliable delivery. TCP is a transport protocol implemented by a transport layer of the IP architecture; the term TCP/IP is commonly used to denote this architecture. The TCP/IP architecture is well known and described in Computer Networks, 3rd Edition, by Andrew S. Tanenbaum, published by Prentice-Hall (1996).
Each BGP node transmits to its peers updates of its routing table. In prior systems there is a fixed interval between (1) the time an update of a path to unit A is sent by unit B to unit C, and (2) a second update of the same path is sent by unit B to unit C. If the interval is too short, the “batching” of a series of updates into a single update message will be reduced or largely eliminated. This can result in “churning”, that is, a unit may receive the first update from a peer after having received the second update from another peer. As a result, there is a substantial increase in the time required for the system to converge on the second update.
The fixed interval is usually a compromise such that it is long enough to provide an acceptably low amount of churning. However this means that in most cases the length of the interval is such as to result in an undesirable latency for the system to converge on a new update.